{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Add to Make Parentheses Valid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAddToMakeValid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使括号有效的最少添加"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>只有满足下面几点之一，括号字符串才是有效的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它是一个空字符串，或者</li>\n",
    "\t<li>它可以被写成&nbsp;<code>AB</code>&nbsp;（<code>A</code>&nbsp;与&nbsp;<code>B</code>&nbsp;连接）, 其中&nbsp;<code>A</code> 和&nbsp;<code>B</code>&nbsp;都是有效字符串，或者</li>\n",
    "\t<li>它可以被写作&nbsp;<code>(A)</code>，其中&nbsp;<code>A</code>&nbsp;是有效字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个括号字符串 <code>s</code> ，在每一次操作中，你都可以在字符串的任何位置插入一个括号</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>s = \"()))\"</code> ，你可以插入一个开始括号为 <code>\"(()))\"</code> 或结束括号为 <code>\"())))\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em>为使结果字符串 <code>s</code> 有效而必须添加的最少括号数</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"())\"\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(((\"\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 只包含&nbsp;<code>'('</code> 和&nbsp;<code>')'</code>&nbsp;字符。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-add-to-make-parentheses-valid](https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-add-to-make-parentheses-valid](https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"())\"', '\"(((\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        need_right = 0\n",
    "        need_left = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                need_left += 1\n",
    "            else:\n",
    "                need_left -= 1\n",
    "                if need_left == -1:\n",
    "                    need_right += 1\n",
    "                    need_left = 0\n",
    "        return need_left + need_right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def minAddToMakeValid(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not S:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for i in range(len(S)):\n",
    "            if S[i] == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                if left != 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "        return ans + left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: 'str') -> 'int':\n",
    "        stack = []\n",
    "        for i in range(len(S)):\n",
    "            if S[i] == \"(\":\n",
    "                stack.append(\"(\")\n",
    "            else:\n",
    "                if len(stack) and stack[-1] == \"(\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(\")\")\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        a ='('\n",
    "        b = ')'\n",
    "        dic ={a:0,b:0}\n",
    "        \n",
    "        re = 0\n",
    "        \n",
    "        for i in range(len(S)):\n",
    "            print(dic,re)\n",
    "            if S[i] == b:\n",
    "                if dic[a] == 0:\n",
    "                    re += 1\n",
    "                else:\n",
    "                    dic[a]-= 1\n",
    "            else:\n",
    "                    dic[a]+=1\n",
    "                    \n",
    "        return re + dic[a]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if S == '':\n",
    "            return 0\n",
    "        stack = []\n",
    "        right_kh_count = 0\n",
    "        left_kh_count = 0\n",
    "        for s in S:\n",
    "            if s == '(':\n",
    "                stack.append(s)\n",
    "            elif s == ')' and stack != []:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                left_kh_count += 1\n",
    "        if stack != []:\n",
    "            right_kh_count = len(stack)\n",
    "        return left_kh_count + right_kh_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = list()\n",
    "        for s in S:\n",
    "            if stack:\n",
    "                if s == \")\" and stack[-1] == \"(\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(s)\n",
    "            else:\n",
    "                stack.append(s)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=921 lang=python3\r\n",
    "#\r\n",
    "# [921] 螺旋矩阵 III\r\n",
    "#\r\n",
    "# https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Medium (64.94%)\r\n",
    "# Total Accepted:    1.7K\r\n",
    "# Total Submissions: 2.7K\r\n",
    "# Testcase Example:  '\"())\"'\r\n",
    "#\r\n",
    "# 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。\r\n",
    "# \r\n",
    "# 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：\r\n",
    "# \r\n",
    "# \r\n",
    "# 它是一个空字符串，或者\r\n",
    "# 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者\r\n",
    "# 它可以被写作 (A)，其中 A 是有效字符串。\r\n",
    "# \r\n",
    "# \r\n",
    "# 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 1：\r\n",
    "# \r\n",
    "# 输入：\"())\"\r\n",
    "# 输出：1\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 2：\r\n",
    "# \r\n",
    "# 输入：\"(((\"\r\n",
    "# 输出：3\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 3：\r\n",
    "# \r\n",
    "# 输入：\"()\"\r\n",
    "# 输出：0\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 4：\r\n",
    "# \r\n",
    "# 输入：\"()))((\"\r\n",
    "# 输出：4\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 提示：\r\n",
    "# \r\n",
    "# \r\n",
    "# S.length <= 1000\r\n",
    "# S 只包含 '(' 和 ')' 字符。\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "#\r\n",
    "class Solution:\r\n",
    "    def minAddToMakeValid(self, S: str) -> int:\r\n",
    "        lstLeft = []\r\n",
    "        for value in S:\r\n",
    "            if value == \"(\":\r\n",
    "                lstLeft.append(\"(\")\r\n",
    "            elif value == \")\":\r\n",
    "                if len(lstLeft)>0:\r\n",
    "                    if lstLeft[-1] ==\"(\":\r\n",
    "                        lstLeft.pop()\r\n",
    "                        continue\r\n",
    "                lstLeft.append(value)\r\n",
    "        return len(lstLeft)\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for p in S:\n",
    "            if res and (p==')') and (res[-1] == '('):\n",
    "                res.pop()\n",
    "            else:\n",
    "                res.append(p)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        for string in S:\n",
    "            if not stack:\n",
    "                stack.append(string)\n",
    "            elif self.isSym(stack[-1], string):\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(string)\n",
    "        return len(stack)\n",
    "\n",
    "    def isSym(self, str1, str2):\n",
    "        print(str1, str2)\n",
    "        return str1==\"(\" and str2==\")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: 'str') -> 'int':\n",
    "        tmp=[]\n",
    "        for s in S:\n",
    "            if tmp:\n",
    "                if tmp[-1]=='(' and s==')':\n",
    "                    tmp.pop()\n",
    "                    continue\n",
    "            tmp.append(s)\n",
    "        return(len(tmp))\n",
    "           \n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# coding=utf-8\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        stack = []\n",
    "        num = 0\n",
    "        for s in S:\n",
    "            if s == '(':\n",
    "                stack.append(s)\n",
    "            if s == ')':\n",
    "                if len(stack) == 0:\n",
    "                    num += 1\n",
    "                else:\n",
    "                    stack.pop()\n",
    "        while stack:\n",
    "            stack.pop()\n",
    "            num += 1\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        stack = []\n",
    "        for ele in S:\n",
    "            if ele is \"(\":\n",
    "                stack.append(ele)\n",
    "            else:\n",
    "                if len(stack) > 0 and stack[-1] is  \"(\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(ele)\n",
    "\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for c in S:\n",
    "            if c == \"(\":\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    res += 1\n",
    "        return len(stack) + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        # 如果遇到“(”，就入栈，否则出栈\n",
    "        # 如果栈为空的情况下遇到')'，那么肯定要加1\n",
    "\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for s in S:\n",
    "            if s == '(':\n",
    "                stack.append(s)\n",
    "            else:\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    res += 1\n",
    "        return res + len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        if len(S) <= 0:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        # 右括号的需求量\n",
    "        need = 0\n",
    "\n",
    "        for c in S:\n",
    "            if c == '(':\n",
    "                need += 1\n",
    "            else:\n",
    "                need -= 1\n",
    "                if need < 0:\n",
    "                    res += 1\n",
    "                    need = 0\n",
    "        return res + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        stack = [\"?\"]\n",
    "        for i in S:\n",
    "            if stack[-1] == '(' and i == \")\":\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return len(stack)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(S)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if S[i] == '(':\n",
    "                stack.append('(')\n",
    "            else:\n",
    "                if not stack:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    stack.pop()\n",
    "        return ans + len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        res=bal=0\n",
    "        for ch in S:\n",
    "            if ch=='(':\n",
    "                bal += 1\n",
    "            else:\n",
    "                bal -= 1\n",
    "            if bal == -1:\n",
    "                bal+=1\n",
    "                res+=1\n",
    "        return bal+res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        def delk(S):\n",
    "            i,n  =0, len(S)\n",
    "            while i < n-1:\n",
    "                if S[i]=='(' and S[i+1]==')':\n",
    "                    return delk(S[:i]+S[i+2:])\n",
    "                i += 1\n",
    "            return S\n",
    "        p = delk(S)\n",
    "        print(p)\n",
    "        return len(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        def delk(S,i):\n",
    "            n  =len(S)\n",
    "            while i < n-1:\n",
    "                if S[i]=='(' and S[i+1]==')':\n",
    "                    return delk(S[:i]+S[i+2:],max(0,i-1))\n",
    "                i += 1\n",
    "            return S\n",
    "        p = delk(S,0)\n",
    "        return len(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, S: str) -> int:\n",
    "        if len(S) == 0:\n",
    "            return 0\n",
    "        m = 0\n",
    "        b = 0\n",
    "        for i in S:\n",
    "            if i == \"(\":\n",
    "                m += 1\n",
    "            elif m >= 1 and i == \")\":\n",
    "                m -= 1\n",
    "            else:\n",
    "                b += 1\n",
    "        return m + b\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        res , need = 0, 0\n",
    "        for c in s:\n",
    "            if c=='(':\n",
    "                need+=1\n",
    "            elif c==')':\n",
    "                need-=1\n",
    "                if need==-1:\n",
    "                    res+=1\n",
    "                    need=0\n",
    "        return res+need\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        q=deque();ans='';c=Counter(s)\n",
    "        for i,num in enumerate(s):\n",
    "            if   num==')':\n",
    "                if q:q.pop();ans += num\n",
    "                else:c[')'] -=1\n",
    "            elif num=='(' :\n",
    "                q.append(i)\n",
    "                if c[')'] >0:ans += num; c[')'] -=1\n",
    "            elif num.isalpha():ans +=num\n",
    "        return len(s)-len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        # 插入次数\n",
    "        result = 0\n",
    "        # 需要的右边括号数量\n",
    "        need = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                need += 1\n",
    "            elif s[i] == ')':\n",
    "                need -= 1\n",
    "\n",
    "                if need == -1:\n",
    "                    need = 0\n",
    "\n",
    "                    # 右阔号太多，插入左阔号\n",
    "                    result += 1\n",
    "\n",
    "        return result + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==\"(\":\n",
    "                stack.append(\"(\")\n",
    "            elif s[i] ==\")\" and stack and stack[-1] == \"(\":\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(\")\")\n",
    "            print(stack)\n",
    "        return len(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "               cur = cur + 1\n",
    "            else:\n",
    "                cur = cur - 1\n",
    "                if cur < 0:\n",
    "                    res += 1\n",
    "                    cur = 0\n",
    "            print(cur,res)\n",
    "        res = res + cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        left_cnt = 0\n",
    "        ret = 0\n",
    "        for c in s:\n",
    "            if c == \")\":\n",
    "                if left_cnt > 0:\n",
    "                    left_cnt -= 1\n",
    "                else:\n",
    "                    ret += 1\n",
    "            else:\n",
    "                left_cnt += 1\n",
    "        return ret + left_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        for c in s:\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "            elif stack[-1]=='(' and c==')':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return len(stack)\n",
    "        '''score,res=0,0\n",
    "        for c in s:\n",
    "            if c=='(':\n",
    "                score+=1\n",
    "            else:\n",
    "               score-=1\n",
    "            if score<0:\n",
    "                res+=1\n",
    "                score+=1\n",
    "        return res+score'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAddToMakeValid(self, s: str) -> int:\n",
    "        need=0\n",
    "        score=0\n",
    "        for i in range(len(s)):\n",
    "            if score>=0 and s[i]=='(':\n",
    "                score+=1\n",
    "\n",
    "            elif score<0 and s[i]==\"(\":\n",
    "                need+=abs(score)\n",
    "                score=1\n",
    "\n",
    "            elif score>0 and s[i]==\")\":\n",
    "                score-=1\n",
    "            \n",
    "            elif score<=0 and s[i]==\")\":\n",
    "                score-=1\n",
    "        \n",
    "        return need+abs(score)\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
